#include <stdio.h>

#define BUFFER_SIZE 10

/* 在指定范围内排序 */
static int innerQuickSort(int *nums, int begin, int end)
{
    if (begin >= end)
    {
        return 0;
    }

    /* 记录基准值 */
    int pivot = nums[begin];

    /* 很重要：备份begin & end */
    int tmpBegin = begin;
    int tmpEnd = end;
    while (begin < end)
    {
        while (begin < end)
        {
            /* 从右向左 */
            if (nums[end] >= pivot)
            {
                end--;
            }
            else
            {
                nums[begin++] = nums[end];
                break;
            }
        }
        while (begin < end)
        {
            /* 从左向右 */
            if (nums[begin] > pivot)
            {
                nums[end--] = nums[begin];
                break;
            }
            else
            {
                begin++;
            }
        }
    }
    /* 退出这个条件 begin == end */
    nums[begin] = pivot;
    /* 递归 */
    /* 第一轮之后注意更新范围，所以前面要备份 */
    innerQuickSort(nums, tmpBegin, begin - 1);
    innerQuickSort(nums, begin + 1, tmpEnd);

}
int quickSort(int *nums, int numSize)
{
    if (nums == NULL)
    {
        return 0;
    }
    return innerQuickSort(nums, 0, numSize - 1);
}

int printNums(int *nums, int numSize)
{
    for (int idx = 0; idx < numSize; idx++)
    {
        printf("%d\t", nums[idx]);
    }
    printf("\n");
}



/* 搜索插入位置 O（log n）复杂度 */

int searchInsert(int* nums, int numSize, int target) 
{
    if (nums == NULL || numSize <= 0)
    {
        return 0;
    }
    /* 起始 */
    int begin = 0;
    /* */
    int end = numSize - 1;
    int ret = -1;

    while (begin <= end)
    {
        /* 更新中间位置 */
        int midIndex = (begin + end) >> 1;

        if (nums[midIndex] == target)
        {
            ret = midIndex + 1;
        }
        else if (nums[midIndex] < target)
        {
            begin = midIndex + 1;
        }
        else if (nums[midIndex] > target)
        {
            end = midIndex - 1;
        }
    }
    if (nums[begin] < target)
    {
        ret = begin + 1;
    }

    return ret;//返回插入值
}

int main()
{
    int nums[BUFFER_SIZE] = {1, 2, 4, 4, 4, 5, 9, 9, 9, 9}; 

    quickSort(nums, BUFFER_SIZE);
    printNums(nums, BUFFER_SIZE);

    int index = searchInsert(nums, BUFFER_SIZE, 4); 
    printf("index:%d\n", index);


    return 0;
}